package org.example.SolutionNew001;

import java.util.*;

public class Window02 {
    public static void main(String[] args) {
        Window02 w = new Window02();
        String s="baa";
        String p="aa";
        System.out.println(w.findAnagrams(s,p));

    }

    public List<Integer> findAnagrams0(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        int n = s.length();
        int m = p.length();
        if(m>n) return res;
        char[] ps = p.toCharArray();
        char[] ss = s.toCharArray();
        Set<Character> pset =new HashSet<>();
        for(char c:ps){
            pset.add(c);
        }
        Set<Character> tmp =new HashSet<>();
        int left = 0;
        for(int i=0; i<n; i++){
            if(!pset.contains(ss[i])){
                left=i+1;tmp.clear();
            }else{
                if(!tmp.contains(ss[i])){
                    tmp.add(ss[i]);
                    if(tmp.size()==m){
                        res.add(left);
                        tmp.remove(ss[left]);
                        left++;
                    }
                }else{
                    tmp.remove(left);
                    left++;
                }
            }
        }
        return res;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sl=s.length();
        int pl=p.length();

        if(pl>sl) return res;
        int[] sa=new int[26];
        int[] pa=new int[26];

        for(int i=0; i<pl; i++){
            sa[s.charAt(i)-'a']++;
            pa[p.charAt(i)-'a']++;
        }

        if(Arrays.equals(sa,pa)){
            res.add(0);
        }

        for(int i=0; i<sl-pl; i++){
            sa[s.charAt(i)-'a']--;
            sa[s.charAt(i+pl)-'a']++;
            if(Arrays.equals(sa,pa)) res.add(i+1);
        }

        return res;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sl=s.length();int pl=p.length();
        if(pl>sl) return res;

        int[] count=new int[26];
        for(int i=0; i<pl; i++){
            count[s.charAt(i)-'a']++;
            count[p.charAt(i)-'a']--;
        }
        int diff=0;
        for(int i=0; i<26; i++){
            if(count[i]!=0) diff++;
        }

        if(diff==0) res.add(0);

        for(int i=0; i<sl-pl; i++){
            if(count[s.charAt(i)-'a']==1){
                diff--;
            }else if(count[s.charAt(i)-'a']==0){
                diff++;
            }
            --count[s.charAt(i)-'a'];
            if(count[s.charAt(i+pl)-'a']==-1){
                diff--;
            }else if(count[s.charAt(i+pl)-'a']==0){
                diff++;
            }
            count[s.charAt(i+pl)-'a']++;
            if(diff==0) res.add(i+1);
        }
        return res;
    }

}
